package lib

func init() {
	Probs = append(Probs, Problem{
		Num:         259,
		Discription: "较小的三数之和组合个数",
		Level:       2,
		Labels: map[string]int{
			"排序":    1,
			"双指针滑动": 1,
		},
	})
}

//注意要求的是下标不能重复，还是值不能重复
func ThreeSumSmaller(nums []int, target int) int {
	n := len(nums)
	//fastSort(nums, 0, n-1)
	count := 0
	for i := 0; i <= n-3; i++ {
		left := i + 1
		right := n - 1
		for left < right {
			sum := nums[i] + nums[left] + nums[right]
			if sum >= target {
				right--
			} else {
				count += right - left
				left++
			}
		}
	}

	return count

}
